3rd solution time complexity is something evil

In the second solution (DP) we only need one row to keep, and we can keep reading from and updating it. That would result in O(n) space instead of O(m*n);

In Python 3.8, there's a new function that calculates n-choose-k directly:

def uniquePaths(self, m: int, n: int) -> int:
    return math.comb(m + n - 2, n - 1)

A bit confused by the code for DP implementation. When you create DP table, you use 'n' as the columns. But in the for loop, to iterate over 'col' you use range(1, m). I understand the output is not affected, but the code causes confusion in understanding

Here is an easy Java Version.

// Runtime: O(M*N) Memory: O(N)
public int uniquePaths(int m, int n) {
	int[] dp = new int[n];
	Arrays.fill(dp, 1);
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			dp[j] = dp[j] + dp[j - 1];
		}
	}
	return dp[n - 1];
}

DP solution doesn't have to hold the whole 2D array.
Only one line needed, so the memory usage becomes O(min(M, N))

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m > n:
            m, n = n, m
        r = [1] * m
        for _ in range(1, n):
            for i in range(1, m):
                r[i] += r[i - 1]
        return r[-1]

Can we not do this in linear time O(m+n) as shown below? I am confused by the statement that, "The best known algorithm to compute factorial function is done by Peter Borwein [and is some crazy complexity]". Honestly I did not read the paper, I was hoping someone could have a layman explanation such as, "because the number of digits grows quickly, multiplication can no longer be thought of as a constant operation".

class Solution {
    public int uniquePaths(int m, int n) {
        double num = 1;
        double denom = 1;
        for(int i = 2; i < Math.min(m,n); i++){
            denom*=i;
        }
        for(int i = Math.max(m,n); i <= m+n-2; i++){
            num*=i;
        }
        return (int) (num/(denom));  
    }
}

The recursion method is quite intuitive, it only needs memorization to pass the tests.

    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        return uniquePaths(memo, m - 1, n - 1);
    }

    private int uniquePaths(int[][] memo, int r, int c) {
        if (r == 0 || c == 0) return memo[r][c] = 1;
        if (memo[r][c] != 0) return memo[r][c];
        return memo[r][c] = uniquePaths(memo, r - 1, c) + uniquePaths(memo, r, c - 1);
    }

The simplest math solution in Java needs BigInteger.

import java.math.BigInteger;

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return factorial(m + n - 2).divide(factorial(m - 1)).divide(factorial(n - 1)).intValue();
    }

    public BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
            result = result.multiply(BigInteger.valueOf(i));
        return result;
    }
}

are we really expected to come up with the apporach 3 solution in a real interview?

I love the illustrations ;) Very subtle Android commercial :P